import entity.TreeNode;

public class ConvertBSTToGreaterTree {
    /*
    * 538. 把二叉搜索树转换为累加树
    * 给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），
    * 使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
    * 提醒一下，二叉搜索树满足下列约束条件：
    * 节点的左子树仅包含键 小于 节点键的节点。
    * 节点的右子树仅包含键 大于 节点键的节点。
    * 左右子树也必须是二叉搜索树。
    *
    * 树中的节点数介于 0 和 10^4 之间。
    * 每个节点的值介于 -10^4 和 10^4 之间。
    * 树中的所有值 互不相同 。
    * 给定的树为二叉搜索树。
    * */
    public static void main(String[] args){

    }

    // 我的想法：从原树中的最大值，也就是新树中的最小值开始递归构建
    // 过啦！
    public TreeNode mySolution(TreeNode root){
        traversal(root);
        return root;
    }
    int sum = 0;
    private void traversal(TreeNode root){
        if(root == null)
            return;
        traversal(root.right);
        root.val += sum;
        sum = root.val;
        traversal(root.left);
    }
}
